/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/k-sum
@Language: C++
@Datetime: 16-02-09 09:03
*/

class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    int kSum(vector<int> A, int k, int target) {
        // wirte your code here
        vector<vector<int> > DP(k+1,vector<int>(target+1,0));
        DP[0][0]=1;
        for(int i=0;i<A.size();++i){
            for(int j=k;j>0;--j)
                for(int t=target;t>=A[i];--t)
                    DP[j][t] += DP[j-1][t-A[i]];
        }
        return DP[k][target];
    }
};